import java.util.*;
/**
 * DifferenzeFinite implementa l'algoritmo delle differenze finite
 * 
 */
public class DifferenzeFinite
{

    //E' una lista delle colonne delle differenze
    //In pratica rappresenta una tabella triangolare
    List <List <Double>> differenze;

    //ascisse dei punti interpolanti
    List <Double> ascisse;

    //costruttore, accetta come parametro una lista rispettivamente 
    //delle ascisse e delle ordinate dei punti iniziali interpolanti
    public DifferenzeFinite(List <Double> x, List <Double> fx)
    {
        ascisse = new ArrayList <Double> (x);
        differenze = new ArrayList < List<Double>> ();
        differenze.add(new ArrayList <Double> (fx));

    }

    //controlla se un arrayList ha tutti gli elementi uguali
    //e' statico perch' non usa metodi definiti dentro la classe.
    //viene usato per sapere se l'algoritmo e' finito, cioe' se l'ultima colonna creata
    //ha tutti gli elementi uguali, il confronto viene fatto tramite equal()
    public static boolean isColonnaUguale(List <Double> colonna)
    {

        System.out.println("is colonna uguale? size="+colonna.size());
        for(int i=0;i<colonna.size();i++)
        {
            for(int j=i+1;j<colonna.size();j++)
            {
                        System.out.println(" "+colonna.get(i)+" vs "+colonna.get(j));
                if(!colonna.get(i).equals(colonna.get(j))) return false;
            }
        }
        return true;

    }

    //true se l'algoritmo e' stato completato
    public boolean isAlgorithmFinished()
    {
        return  isColonnaUguale(differenze.get(differenze.size()-1));
    }

    //fa avanzare l'algoritmo di un passo: calcola i rapporti incrementali per l'ultima colonna inserita
    //la prima volta che viene eseguito, comincia quindi dalle ordinate.
    //ritorna true se l'algoritmo e' stato terminato 
    public boolean step()
    {
        if(!isAlgorithmFinished()) { //controlla che l'algoritmo non sia finito

            int dim = differenze.size();   
            List <Double> colonna = new ArrayList<Double>(); //inizializza la nuova colonna che verr? aggiunta
            List <Double> colonna_prec = differenze.get(dim-1); //preleva l'ultima colonna inserita

            //cicla dal primo al penultimo elemento dell'ultima colonna insertia

            for(int i=0;i<colonna_prec.size()-1;i++)
            {
                //  System.out.println("colonna "+i);

                double delta =colonna_prec.get(i+1)-colonna_prec.get(i); //differenza di un elemento col successivo

                int x1=(i+dim);
                int x2=(i-dim);
                int medio = dim+i*2;
                int differenzaCelle = dim;
                double diff = ascisse.get((medio+differenzaCelle)/2)-ascisse.get((medio-differenzaCelle)/2);
                colonna.add(delta/diff);
            }
            differenze.add(colonna); //aggiungne la nuova colonna alla tabella
            return isColonnaUguale(colonna); //se la colonna ha tutti gli elementi uguali l'algoritmo e' finito

        }else //se mi trovo qua vuol dire  che isAlgorithmFinished()=true
        {

            return true; 
        }
    }

    public void solve()
    {
        while(step());
    }

    //calcola il polinomio in un punto x e ne ritorna il valore,
    //lancia un eccezione AlgorithmNotFinishedException se si prova ad interpolare il polinomio prima che l'algoritmo sia stato terminato
    public double p (double x)  throws  AlgorithmNotFinishedException
    {
        double result=0;

        for(int i=0;i<ascisse.size()-1;i++)
        {
            double prodotto=1;
            for (int j=0;j<i;j++)
            {
                prodotto = prodotto * (x-ascisse.get(j)); //calcola la produttoria (di lagrange?)
            }
            result += b(i)*prodotto;

        }
        return result;
    }

    //restituisce una stringa rappresentante il polinomio
    //lancia un eccezione AlgorithmNotFinishedException se si prova ad interpolare il polinomio prima che l'algoritmo sia stato terminato
    public String polinomio () throws AlgorithmNotFinishedException
    {
        String s = "";
        for(int i=0;i<ascisse.size()-1;i++)
        {

            String t="(x-"+ascisse.get(0)+")";
            for (int j=1;j<i;j++)
            {
                t+=" * (x-"+ascisse.get(i)+")";
            }
            s+=" + "+t+" * "+b(i);
        }
        return s;

    }

    //calcola i coefficenti b (vedi pdf mirolo)
    //lancia un eccezione AlgorithmNotFinishedException se si prova ad interpolare il polinomio prima che l'algoritmo sia stato terminato
    public double b(int n) throws  AlgorithmNotFinishedException
    {
        try
        {
            double c= differenze.get(n).get(0);
            double diff=(ascisse.get(n)-ascisse.get(0));
            return c;
        }
        catch(IndexOutOfBoundsException e)
        {
            throw    new  AlgorithmNotFinishedException();
        }
    }

    //print della tabella triangolare usata durante il debug
    public void print()
    {
        for(int i=0;i<differenze.size();i++)
        {
            List <Double> colonna = differenze.get(i);
            System.out.println(i);
            for(int j=0;j<colonna.size();j++)
                System.out.println("\t"+colonna.get(j));

        }

    }

    //restituisce una tabella compatibile con JTabella
    //la prima colonna contiene le ascisse, poi le ordinate, poi le varie differenze
    public ArrayList<ArrayList<Double>> getData() {
        ArrayList<ArrayList<Double>> als = new ArrayList<ArrayList<Double>>();
        als.add(     (ArrayList <Double>) ascisse);
        for(List <Double> l: differenze)
            als.add((ArrayList<Double>)l );
        return als;
    }

}
